Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Best, Worst, and Average Cases

Let’s build on our analysis of insertion sort from the previous lesson. We’ve already covered the general time complexity of insertion sort. In this lesson, we’ll analyze how insertion sort performs in the best, average, and worst cases by calculating time complexity for each scenario.

Insertion Sort: Case Analysis

Insertion sort works by gradually building a sorted section of the list by inserting each new element into its correct position. The time it takes for each insertion depends on where the element needs to be placed, making the input order critical to the algorithm’s performance.

1. Best Case: Already Sorted List

In the best case, the input list is already sorted.

Image

Here’s how insertion sort behaves:

  • Inner Loop: The inner while loop checks if the current element is greater than the previous one. Since the list is already sorted, this condition arr[j] > key is always False on the first comparison for each element, and the loop does not run.
  • Number of Operations: For each element, the inner loop performs one comparison and then exits, taking constant time for each element.

Mathematically, the total number of comparisons is:

Since the time complexity for each of the elements is constant, the best-case time complexity of insertion sort is .

2. Worst Case: Reverse Sorted List

In the worst case, the input list is sorted in reverse order, meaning every element must be moved to the beginning of the sorted section.

Image
  • Inner Loop: For each element, the inner while loop must shift all previous elements to make space. This means for the second element, one comparison and shift occur; for the third, two comparisons and shifts; and so forth.

  • Number of Operations: The first element requires 0 comparisons, the second requires 1, the third requires 2, and so on, up to comparisons for the last element.

The total number of comparisons and shifts in the worst case is:

This sum is approximately . Thus, the worst-case time complexity of insertion sort is .

3. Average Case: Randomly Ordered List

In the average case, we assume that the input list is randomly ordered. The number of comparisons for each element depends on where it needs to be inserted within the sorted section. On average, each element is compared with half of the elements in the sorted portion.

Image
  • Inner Loop: For each insertion, the inner while loop is expected to run about half as many times as in the worst case.
  • Number of Operations: For each element, we perform approximately comparisons, where is the current position of the element in the loop.

The total number of comparisons is roughly:

Ignoring constant factors, the average-case time complexity is .

Summary of Time Complexity for Insertion Sort

CaseTime Complexity
Best Case
Average Case
Worst Case

In the next lesson, Common Time Complexities, we’ll explore typical time complexities like , , and , and how these appear across various algorithms.

Analyzing Simple Algorithms
Constant Time: O(1)
Mark as Completed

On this page

Insertion Sort: Case Analysis

  1. Best Case: Already Sorted List
  1. Worst Case: Reverse Sorted List
  1. Average Case: Randomly Ordered List

Summary of Time Complexity for Insertion Sort